Accelerating Lattice Reduction with FPGAs
Identifieur interne : 007349 ( Main/Exploration ); précédent : 007348; suivant : 007350Accelerating Lattice Reduction with FPGAs
Auteurs : Jérémie Detrey [France] ; Guillaume Hanrot [France] ; Xavier Pujol [France] ; Damien Stehlé [Australie, France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2010.
Descripteurs français
- Wicri :
- topic : Cryptographie, Logiciel, Prix unitaire.
English descriptors
- KwdEn :
- Actual number, Algorithm, Bottom layer, Clock cycles, Communication cost, Control unit, Corresponding subtree, Cryptography, Cryptology, Cryptosystems, Detrey, Enumerating vectors, Enumeration, Enumeration algorithm, Enumeration tree, Euclidean lattices, Fpga, Fpga accelerator, Fpga implementation, Fpgas, Gaussian, Gaussian approximation, Gaussian estimate, Gaussian heuristic, Granularity, Granularity level, Heidelberg, Heuristic, Homomorphic encryption, Ideal lattices, Implementation, Input basis, Integer part, Intel core, Lattice, Lattice attacks, Lattice problems, Lattice reduction, Lncs, Local variables, Master machine, Matrix, Memory requirements, Multiplier, Nguyen, Node, Parallel implementation, Parallelization, Parallelization technique, Partial sums, Performance estimations, Pohst enumeration algorithm, Possible values, Proc, Randomized reductions, Real number, Resource usage, Schmidt matrix, Short vectors, Shortest, Shortest lattice vector, Shortest lattice vector problem, Shortest vector, Shortest vector problem, Software, Software implementation, Solver, Space complexities, Speed grade, Sphere decoding, Springer, Squared norm, Stehl, Stoc, Subtree, Subtrees, Total traversal rate, Traversal, Traversal rate, Unit price, Whole enumeration tree.
- Teeft :
- Actual number, Algorithm, Bottom layer, Clock cycles, Communication cost, Control unit, Corresponding subtree, Cryptography, Cryptology, Cryptosystems, Detrey, Enumerating vectors, Enumeration, Enumeration algorithm, Enumeration tree, Euclidean lattices, Fpga, Fpga accelerator, Fpga implementation, Fpgas, Gaussian, Gaussian approximation, Gaussian estimate, Gaussian heuristic, Granularity, Granularity level, Heidelberg, Heuristic, Homomorphic encryption, Ideal lattices, Implementation, Input basis, Integer part, Intel core, Lattice, Lattice attacks, Lattice problems, Lattice reduction, Lncs, Local variables, Master machine, Matrix, Memory requirements, Multiplier, Nguyen, Node, Parallel implementation, Parallelization, Parallelization technique, Partial sums, Performance estimations, Pohst enumeration algorithm, Possible values, Proc, Randomized reductions, Real number, Resource usage, Schmidt matrix, Short vectors, Shortest, Shortest lattice vector, Shortest lattice vector problem, Shortest vector, Shortest vector problem, Software, Software implementation, Solver, Space complexities, Speed grade, Sphere decoding, Springer, Squared norm, Stehl, Stoc, Subtree, Subtrees, Total traversal rate, Traversal, Traversal rate, Unit price, Whole enumeration tree.
Abstract
Abstract: We describe an FPGA accelerator for the Kannan–Fincke–Pohst enumeration algorithm (KFP) solving the Shortest Lattice Vector Problem (SVP). This is the first FPGA implementation of KFP specifically targeting cryptographically relevant dimensions. In order to optimize this implementation, we theoretically and experimentally study several facets of KFP, including its efficient parallelization and its underlying arithmetic. Our FPGA accelerator can be used for both solving stand-alone instances of SVP (within a hybrid CPU–FPGA compound) or myriads of smaller dimensional SVP instances arising in a BKZ-type algorithm. For devices of comparable costs, our FPGA implementation is faster than a multi-core CPU implementation by a factor around 2.12.
Url:
DOI: 10.1007/978-3-642-14712-8_8
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000789
- to stream Istex, to step Curation: 000789
- to stream Istex, to step Checkpoint: 000C66
- to stream Main, to step Merge: 007885
- to stream Main, to step Curation: 007349
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Accelerating Lattice Reduction with FPGAs</title>
<author><name sortKey="Detrey, Jeremie" sort="Detrey, Jeremie" uniqKey="Detrey J" first="Jérémie" last="Detrey">Jérémie Detrey</name>
</author>
<author><name sortKey="Hanrot, Guillaume" sort="Hanrot, Guillaume" uniqKey="Hanrot G" first="Guillaume" last="Hanrot">Guillaume Hanrot</name>
</author>
<author><name sortKey="Pujol, Xavier" sort="Pujol, Xavier" uniqKey="Pujol X" first="Xavier" last="Pujol">Xavier Pujol</name>
</author>
<author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:2900FDFB0BEF6C5C276B9C3D2F9414F9305194EF</idno>
<date when="2010" year="2010">2010</date>
<idno type="doi">10.1007/978-3-642-14712-8_8</idno>
<idno type="url">https://api.istex.fr/document/2900FDFB0BEF6C5C276B9C3D2F9414F9305194EF/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000789</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000789</idno>
<idno type="wicri:Area/Istex/Curation">000789</idno>
<idno type="wicri:Area/Istex/Checkpoint">000C66</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000C66</idno>
<idno type="wicri:doubleKey">0302-9743:2010:Detrey J:accelerating:lattice:reduction</idno>
<idno type="wicri:Area/Main/Merge">007885</idno>
<idno type="wicri:Area/Main/Curation">007349</idno>
<idno type="wicri:Area/Main/Exploration">007349</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Accelerating Lattice Reduction with FPGAs</title>
<author><name sortKey="Detrey, Jeremie" sort="Detrey, Jeremie" uniqKey="Detrey J" first="Jérémie" last="Detrey">Jérémie Detrey</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>CARAMEL project-team, LORIA, INRIA / CNRS / Nancy Université, Campus Scientifique, BP 239, F-54506, Vandœuvre-lès-Nancy Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Hanrot, Guillaume" sort="Hanrot, Guillaume" uniqKey="Hanrot G" first="Guillaume" last="Hanrot">Guillaume Hanrot</name>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire LIP, CNRS-ENSL-INRIA-UCBL, ÉNS Lyon, Université de Lyon, 46 Allée d’Italie, 69364, Lyon Cedex 07</wicri:regionArea>
<wicri:noRegion>69364, Lyon Cedex 07</wicri:noRegion>
<wicri:noRegion>Lyon Cedex 07</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Pujol, Xavier" sort="Pujol, Xavier" uniqKey="Pujol X" first="Xavier" last="Pujol">Xavier Pujol</name>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire LIP, CNRS-ENSL-INRIA-UCBL, ÉNS Lyon, Université de Lyon, 46 Allée d’Italie, 69364, Lyon Cedex 07</wicri:regionArea>
<wicri:noRegion>69364, Lyon Cedex 07</wicri:noRegion>
<wicri:noRegion>Lyon Cedex 07</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name>
<affiliation wicri:level="1"><country xml:lang="fr">Australie</country>
<wicri:regionArea>CNRS, Macquarie University and University of Sydney, Dpt. of Mathematics and Statistics, University of Sydney, 2006, NSW</wicri:regionArea>
<wicri:noRegion>NSW</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2010</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Actual number</term>
<term>Algorithm</term>
<term>Bottom layer</term>
<term>Clock cycles</term>
<term>Communication cost</term>
<term>Control unit</term>
<term>Corresponding subtree</term>
<term>Cryptography</term>
<term>Cryptology</term>
<term>Cryptosystems</term>
<term>Detrey</term>
<term>Enumerating vectors</term>
<term>Enumeration</term>
<term>Enumeration algorithm</term>
<term>Enumeration tree</term>
<term>Euclidean lattices</term>
<term>Fpga</term>
<term>Fpga accelerator</term>
<term>Fpga implementation</term>
<term>Fpgas</term>
<term>Gaussian</term>
<term>Gaussian approximation</term>
<term>Gaussian estimate</term>
<term>Gaussian heuristic</term>
<term>Granularity</term>
<term>Granularity level</term>
<term>Heidelberg</term>
<term>Heuristic</term>
<term>Homomorphic encryption</term>
<term>Ideal lattices</term>
<term>Implementation</term>
<term>Input basis</term>
<term>Integer part</term>
<term>Intel core</term>
<term>Lattice</term>
<term>Lattice attacks</term>
<term>Lattice problems</term>
<term>Lattice reduction</term>
<term>Lncs</term>
<term>Local variables</term>
<term>Master machine</term>
<term>Matrix</term>
<term>Memory requirements</term>
<term>Multiplier</term>
<term>Nguyen</term>
<term>Node</term>
<term>Parallel implementation</term>
<term>Parallelization</term>
<term>Parallelization technique</term>
<term>Partial sums</term>
<term>Performance estimations</term>
<term>Pohst enumeration algorithm</term>
<term>Possible values</term>
<term>Proc</term>
<term>Randomized reductions</term>
<term>Real number</term>
<term>Resource usage</term>
<term>Schmidt matrix</term>
<term>Short vectors</term>
<term>Shortest</term>
<term>Shortest lattice vector</term>
<term>Shortest lattice vector problem</term>
<term>Shortest vector</term>
<term>Shortest vector problem</term>
<term>Software</term>
<term>Software implementation</term>
<term>Solver</term>
<term>Space complexities</term>
<term>Speed grade</term>
<term>Sphere decoding</term>
<term>Springer</term>
<term>Squared norm</term>
<term>Stehl</term>
<term>Stoc</term>
<term>Subtree</term>
<term>Subtrees</term>
<term>Total traversal rate</term>
<term>Traversal</term>
<term>Traversal rate</term>
<term>Unit price</term>
<term>Whole enumeration tree</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en"><term>Actual number</term>
<term>Algorithm</term>
<term>Bottom layer</term>
<term>Clock cycles</term>
<term>Communication cost</term>
<term>Control unit</term>
<term>Corresponding subtree</term>
<term>Cryptography</term>
<term>Cryptology</term>
<term>Cryptosystems</term>
<term>Detrey</term>
<term>Enumerating vectors</term>
<term>Enumeration</term>
<term>Enumeration algorithm</term>
<term>Enumeration tree</term>
<term>Euclidean lattices</term>
<term>Fpga</term>
<term>Fpga accelerator</term>
<term>Fpga implementation</term>
<term>Fpgas</term>
<term>Gaussian</term>
<term>Gaussian approximation</term>
<term>Gaussian estimate</term>
<term>Gaussian heuristic</term>
<term>Granularity</term>
<term>Granularity level</term>
<term>Heidelberg</term>
<term>Heuristic</term>
<term>Homomorphic encryption</term>
<term>Ideal lattices</term>
<term>Implementation</term>
<term>Input basis</term>
<term>Integer part</term>
<term>Intel core</term>
<term>Lattice</term>
<term>Lattice attacks</term>
<term>Lattice problems</term>
<term>Lattice reduction</term>
<term>Lncs</term>
<term>Local variables</term>
<term>Master machine</term>
<term>Matrix</term>
<term>Memory requirements</term>
<term>Multiplier</term>
<term>Nguyen</term>
<term>Node</term>
<term>Parallel implementation</term>
<term>Parallelization</term>
<term>Parallelization technique</term>
<term>Partial sums</term>
<term>Performance estimations</term>
<term>Pohst enumeration algorithm</term>
<term>Possible values</term>
<term>Proc</term>
<term>Randomized reductions</term>
<term>Real number</term>
<term>Resource usage</term>
<term>Schmidt matrix</term>
<term>Short vectors</term>
<term>Shortest</term>
<term>Shortest lattice vector</term>
<term>Shortest lattice vector problem</term>
<term>Shortest vector</term>
<term>Shortest vector problem</term>
<term>Software</term>
<term>Software implementation</term>
<term>Solver</term>
<term>Space complexities</term>
<term>Speed grade</term>
<term>Sphere decoding</term>
<term>Springer</term>
<term>Squared norm</term>
<term>Stehl</term>
<term>Stoc</term>
<term>Subtree</term>
<term>Subtrees</term>
<term>Total traversal rate</term>
<term>Traversal</term>
<term>Traversal rate</term>
<term>Unit price</term>
<term>Whole enumeration tree</term>
</keywords>
<keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Cryptographie</term>
<term>Logiciel</term>
<term>Prix unitaire</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We describe an FPGA accelerator for the Kannan–Fincke–Pohst enumeration algorithm (KFP) solving the Shortest Lattice Vector Problem (SVP). This is the first FPGA implementation of KFP specifically targeting cryptographically relevant dimensions. In order to optimize this implementation, we theoretically and experimentally study several facets of KFP, including its efficient parallelization and its underlying arithmetic. Our FPGA accelerator can be used for both solving stand-alone instances of SVP (within a hybrid CPU–FPGA compound) or myriads of smaller dimensional SVP instances arising in a BKZ-type algorithm. For devices of comparable costs, our FPGA implementation is faster than a multi-core CPU implementation by a factor around 2.12.</div>
</front>
</TEI>
<affiliations><list><country><li>Australie</li>
<li>France</li>
</country>
<region><li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<settlement><li>Vandœuvre-lès-Nancy</li>
</settlement>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Detrey, Jeremie" sort="Detrey, Jeremie" uniqKey="Detrey J" first="Jérémie" last="Detrey">Jérémie Detrey</name>
</region>
<name sortKey="Detrey, Jeremie" sort="Detrey, Jeremie" uniqKey="Detrey J" first="Jérémie" last="Detrey">Jérémie Detrey</name>
<name sortKey="Hanrot, Guillaume" sort="Hanrot, Guillaume" uniqKey="Hanrot G" first="Guillaume" last="Hanrot">Guillaume Hanrot</name>
<name sortKey="Hanrot, Guillaume" sort="Hanrot, Guillaume" uniqKey="Hanrot G" first="Guillaume" last="Hanrot">Guillaume Hanrot</name>
<name sortKey="Pujol, Xavier" sort="Pujol, Xavier" uniqKey="Pujol X" first="Xavier" last="Pujol">Xavier Pujol</name>
<name sortKey="Pujol, Xavier" sort="Pujol, Xavier" uniqKey="Pujol X" first="Xavier" last="Pujol">Xavier Pujol</name>
<name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name>
</country>
<country name="Australie"><noRegion><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 007349 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 007349 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Asie |area= AustralieFrV1 |flux= Main |étape= Exploration |type= RBID |clé= ISTEX:2900FDFB0BEF6C5C276B9C3D2F9414F9305194EF |texte= Accelerating Lattice Reduction with FPGAs }}
This area was generated with Dilib version V0.6.33. |